//K 次取反后最⼤化的数组和（easy）： https://leetcode.cn/problems/maximize-sum-of-array-after-k-negations/
class Solution
{
public:
	int largestSumAfterKNegations(vector<int>& nums, int k)
	{
		int m = 0, minElem = INT_MAX, n = nums.size();
		for (auto x : nums)
		{
			if (x < 0)
			{
				m++;
			}
			minElem = min(minElem, abs(x)); // 求绝对值最⼩的那个数
		}
		// 分类讨论
		int ret = 0;
		if (m > k)
		{
			sort(nums.begin(), nums.end());
			for (int i = 0; i < k; i++) // 前 k ⼩个负数，变成正数
			{
	
			ret += -nums[i];
			}
			for (int i = k; i < n; i++) // 后⾯的数不变
			{
				ret += nums[i];
			}
		}
		else
		{
			// 把所有的负数变成正数
			for (auto x : nums) ret += abs(x);
			if ((k - m) % 2) // 判断是否处理最⼩的正数
			{
				ret -= minElem * 2;
			}
		}
		return ret;
	}
};

//按⾝⾼排序（easy）: https://leetcode.cn/problems/sort-the-people/
class Solution
{
public:
	vector<string> sortPeople(vector<string>& names, vector<int>& heights)
	{
		// 1. 创建⼀个下标数组
		int n = names.size();
		vector<int> index(n);
		for (int i = 0; i < n; i++)
		{
			index[i] = i;
		}
		// 2. 对下标进⾏排序
		sort(index.begin(), index.end(), [&](int i, int j)
			{
				return heights[i] > heights[j];
			});
		// 3. 提取结果
		vector<string> ret;
		for (int i : index)
		{
				ret.push_back(names[i]);
		}
		return ret;
	}
};